// 60. 第k个排列


/**
 * 直接回溯生成所有的,排序    five方法
 * @param n 
 * @param k 
 */
function getPermutation_FIVE(n: number, k: number): string {



    function generate(start:number):string[] {
        // console.log(start)
        if(start==n){
            return [(''+n)]
        }
        let res:string[] = generate(start+1)
        let re:string[] = []
        for (const it of res) {
            // console.log("进来了")
            for(let i=0;i<=it.length;i++){
                let tmp:string = it.substring(0,i)+start+it.substring(i)
                re.push(tmp)
            }
        }
        return re
    }
    const ans:string[] = generate(1).sort((a:string,b:string):number =>{
        return a>b?1:-1
    })
    return ans[k-1]
};


/**
 * 通过判断元素个数获取每位的数量
 * @param n 
 * @param k 
 */
function getPermutation(n: number, k: number): string {
    let FACT = []
    FACT.push(1)
    //计算阶乘
    let fact = 1
    for (let index =1;  index <n ; index++){
        fact*=index
        FACT.push(fact)
    }
    let used:boolean[] = new Array(n+1)
    used.fill(false)
    let ans = ''
    k--
    for (let index =0; index<n;index++){
        const f = FACT[n-1-index]
        const target = Math.floor(k/f)+1
        let nums = 0
        for(let i=1;i<used.length;i++){
            let t = used[i]
            if(!t)nums++
            if(nums==target&&!t){
                ans += i
                used[i] = true
                break
            }
        }
        k%=f
    }
    return ans
};

const n =3
const k =3
console.log(getPermutation(n,k)) 